﻿using System.Collections.Generic;
using TicketReservationSystem.Common.Entities;
using TicketReservationSystem.Common.Interfaces;

namespace TicketReservationSystem.FlightSearch
{
    public class FlightSearch : IFlightSearch
    {
        private readonly IDataAccess data;

        public FlightSearch(IDataAccess data)
        {
            this.data = data;
        }

        public IList<Flight> SearchPath(City departure, City destination)
        {
            var path = Search(departure, destination);

            if (path == null) return null;

            var flights = data.AllFlights();
            var result = new List<Flight>();

            for (var i = 0; i < path.Count - 1; i++)
            {
                foreach (var flight in flights)
                {
                    if (flight.Departure.ID == path[i].ID && flight.Destination.ID == path[i + 1].ID)
                    {
                        result.Add(flight);
                        break;
                    }
                }
            }

            return result;
        }

        public IList<Flight> GetAll()
        {
            return data.AllFlights();
        }

        private IList<Airport> Search(City departure, City destination)
        {
            var path = new Stack<Airport>();

            var airportsInDepartureCity = data.AllAirportsInCity(departure);
            var airportsInDestinationCity = data.AllAirportsInCity(destination);

            foreach (var departureAirport in airportsInDepartureCity)
            {
                var parent = BFS(departureAirport);

                foreach (var destinationAirport in airportsInDestinationCity)
                {
                    path.Clear();

                    var point = destinationAirport;

                    while (point != null)
                    {
                        path.Push(point);
                        point = parent[point.ID - 1];
                    }

                    if (path.Count != 0 && path.Peek().ID == departureAirport.ID)
                    {
                        var result = new List<Airport>();

                        while (path.Count != 0)
                        {
                            result.Add(path.Pop());
                        }

                        return result;
                    }
                }
            }

            return null;
        }

        private List<Airport>[] BuildAdjacencyList()
        {
            var airports = data.AllAirports();

            var list = new List<Airport>[airports.Count];

            for (var i = 0; i < airports.Count; i++)
            {
                list[i] = new List<Airport>();
            }

            var flights = data.AllFlights();

            foreach (var flight in flights)
            {
                list[flight.Departure.ID - 1].Add(flight.Destination);
            }

            return list;
        }

        private Airport[] BFS(Airport start)
        {
            var airports = data.AllAirports();
            var adjacencyList = BuildAdjacencyList();

            var color = new int[adjacencyList.Length];
            var transfer = new int[adjacencyList.Length];
            var parent = new Airport[adjacencyList.Length];

            for (var i = 0; i < adjacencyList.Length; i++)
            {
                color[i] = 0;
                transfer[i] = -1;
                parent[i] = null;
            }

            var queue = new Queue<Airport>();

            color[start.ID - 1] = 1;
            transfer[start.ID - 1] = 0;
            queue.Enqueue(airports[start.ID - 1]);

            while (queue.Count != 0)
            {
                var airport = queue.Dequeue();

                foreach (var item in adjacencyList[airport.ID - 1])
                {
                    if (color[item.ID - 1] == 0)
                    {
                        color[item.ID - 1] = 1;
                        transfer[item.ID - 1] = transfer[airport.ID - 1] + 1;
                        parent[item.ID - 1] = airport;
                        queue.Enqueue(item);
                    }
                }

                color[airport.ID - 1] = 2;
            }

            return parent;
        }
    }
}
